Conventional software applications, such as word processors, create page-based documents where each page may contain one or more graphical objects (ie., text, lines, fill regions and/or image data). When representing such documents on a display device or a printing device, a software application typically sends commands to the device. These commands are typically defined by graphical interface services associated with a native operating system which is executing the software application. One such operating system is Windows™. The graphics interface services of the Windows™ operating system are typically referred to as a graphics device interface (GDI) layer. The GDI layer may be implemented as an application programming interface (API) being executed by the operating system and providing a rich set of graphics features to software applications being executed by the operating system.
A graphics rendering system typically renders graphical objects received from the GDI layer of an operating system, generating pixels. Rendering is the process by which graphical objects received from the GDI layer are converted to pixels by a graphics rendering system. The pixels generated by the graphics rendering system are then sent to an output device for display and/or printing.
FIG. 1 shows the relationship between a conventional software application 110, a graphics device interface layer 120, a graphics rendering system 130 and a target device 140. The application 110 passes each page of a document as a series of commands. For each page to be rendered, the series of commands are defined in terms of graphic interface services which describe the graphical objects of the page. The GDI layer 120 mediates between the application program 110 and the target device 140. The GDI layer 120 enables the graphics rendering system 130 to support a much smaller set of functionality than the Windows™ operating system can handle. The GDI layer 120 also provides graphical objects to the graphics rendering system 130 in a format that the GDI layer 120 determines is the most efficient for the graphics rendering system 130 and at a resolution of the target device 140. The graphics rendering system 130 then renders the graphical objects received from the GDI layer 120, generating pixels. The pixels generated by the graphics rendering system 120 are then sent to the target device 140.
There are a wide range of graphics software applications. Many of these graphics software applications are capable of producing complex graphical objects. These objects are usually specific to a particular graphics software application. For example, one well known graphics software application referred to as Corel Draw™ can create a complex object know as a ‘fountain fill’. A ‘fill’ is used to describe pixel data that a graphical object is painted (ie., filled) with. For example, a red square has a red flat coloured fill. A fountain fill is a type of ‘gradient fill’ which describes the fill of an object where two or more colours of the object flow into each other smoothly. Gradient fills come in many types (eg., linear, conical, radial and non-linear). An object 210 filled with a radial gradient fill is shown in FIG. 2A. A gradient fill transition usually consists of one colour flowing into another. However, more complex gradient fills may have many transitions between many different colours. FIG. 2B shows an example of an object 220 filled with a gradient fill that has many transitions.
The method used by a particular graphics software application for filling an object with a linear gradient fill is dependent on the particular graphics software application. However, one known method of filling an object with a linear gradient fill comprises the step of specifying a start colour and an end colour at each end of the bounding box of a graphical object being filled and interpolating between the start and end colour.
Complex graphical objects such as the objects 210 and 220 are not typically able to be directly rendered by a printer or display driver. Therefore, a GDI layer typically passes gradient fills to a graphics rendering system as a number of flat filled adjacent objects in the form of parallelograms. These flat filled adjacent parallelograms enable the graphics rendering system to render a complex graphical object without the need to support any application specific graphics types. For renderers which use a Painters Algorithm method of rendering, flat filled parallelograms may be rendered to a frame store. However, since both linear and non-linear gradient fills are typically passed by the GDI layer as flat filled parallelograms, the width of any two adjacent parallelograms is not typically consistent. As a result, colour change between consecutive sets of these parallelograms is not always linear.
In some graphics rendering systems, the rendering process is a two-stage process. In such rendering systems, graphical objects of a page to be rendered are firstly converted into an intermediate format before the rendering process begins. This intermediate format is known as a ‘display list’. In one such graphics rendering system, the first stage of the rendering process converts each graphical object of the page received from an associated operating system into an intermediate edge-based object. For example, FIG. 3 shows a conventional graphics rendering system 330 that converts each received graphical object into an intermediate edge-based object. In the example of FIG. 3, a linear gradient fill 370 corresponding to a complex graphical object, created by a graphics application 310 is passed to the graphics rendering system 330 from the graphics device interface 320, as a number of flat coloured rectangles (eg., the flat coloured rectangle 380). A display list creation module 340 of the graphics rendering system 330, converts each of the flat coloured rectangles 380 into two edges, a level, and fill data, which are stored in databases (eg., 381, 382 and 383, respectively). The edges describe the area in which each flat coloured rectangle 380 is filled. The fill data provides the colour/opacity of the pixels inside the edges of the flat coloured rectangle 380. The fill data may be a flat colour, a bitmap, an equation or pattern that describes pixel data at a specific position within the flat coloured rectangle 380. The level contains important rendering information such as a z-order for the coloured rectangle 380, the raster operation to be applied to the fill data and whether an associated edge is a clipping edge or a filling edge.
Before the graphics rendering system 330 can render one of the flat coloured rectangles 380, each rectangle must be sorted, such that all edges of a particular rectangle are sorted in ascending y, then ascending x order. The y and x coordinates correspond respectively to the scan lines and pixel locations on each scan line in a rasterized rendering system. The graphics rendering system generates a display list 350 of edges and their associated fill priority (z-order), along with other information such as if an edge is a clipping edge or a filling edge.
A display list 350 is sometimes referred to as a job. The job comprises all of the information needed by a rendering module 360 of the graphics rendering system 330 to render the page. The rendering of the page by the rendering module 360 is the second stage of the rendering process.
The rendering module 360 parses the job and generates pixels for a downstream device such a printer, for each scanline down the page. For each scanline, as the rendering module 360 encounters the left edge of a coloured rectangle (eg., the rectangle 380), the rendering module 360 loads the level associated with the rectangle into an intermediate buffer. The level associated with the rectangle is now said to be active. The level associated with the rectangle is deactivated when the rendering module 360 encounters the right edge of the rectangle.
The rendering module 360 allows for different types of activation rules for edges, which will be explained later in this document. The pixel span between each set of edges on a scanline is rendered according to these rules. When the rendering module 360 encounters an edge, the rendering module 360 determines a top most (ie., greatest z-order position) currently active level and renders the pixels according to the fill data of the top most currently active level. If the object (eg., a flat filled rectangle) corresponding to the top most level is transparent, then compositing of lower z-order levels is used to calculate the resulting pixel data. Every edge the rendering module 360 encounters has to be updated to a new position on a next scanline. In addition, since edges may cross one another, edges must also be sorted to ensure that the edges remain in ascending x order. The rendering process continues on a scanline per scanline basis until all the pixels on the page are rendered.
As described above, complex objects are typically broken down into simpler objects, such as flat filled rectangles, by the graphics device interface 320. Each of these simpler objects has to be converted to the intermediate form separately, which takes considerable time. When rendering each individual flat fill object, each of the edges of the object need to be sorted and each edge updated for every scanline, which is also a time consuming process for the rendering module 360. So, for a complex object that has been broken down into hundreds of simpler objects, converting each object into an intermediate edge based format and rendering the complex object using an edge based rendering module is highly inefficient.
As an example, the horizontal linear gradient fill 230 shown in FIG. 2C may be broken down into two hundred and fifty six (256) flat fill rectangles by the graphics device interface 320 before being passed to the graphics rendering system 330. In the worst case of the gradient fill 230 proceeding left to right or right to left, all two hundred and fifty-six (256) flat fills become active on a scanline, equating to five hundred and twelve (512) edges per scanline. Hence for an edge-based rendering system, such a method of rendering is considerably inefficient, due to the large amount of edge sorting and tracking that needs to be performed per scanline. In addition, each flat fill must be stored into an intermediate object-graphics format, accessed for each fill-path for each scanline and then all of the edges sorted before rendering can begin.
The above rendering method requires large amounts of memory accesses and can also consume large amounts of fill resources when the number of flat fills to be processed is in the order of thousands. Such numbers of flat fills can occur frequently when printing pages larger than A3 at high-resolutions.
One way to increase the rendering performance of the edge based rendering module 360, when rendering the gradient fill 230, is to reduce the number of edge updates and the amount of edge sorting that needs to be carried out. One known method of reducing edge updates and sorting is to remove redundant edges where possible by compiling graphical objects into a larger single graphic object or into a more complex object that a rendering module can handle. There are a number of known methods for compiling graphical objects into a larger single graphical object. For example, two separate adjacent bitmaps may be stitched together to form one large bitmap, two contiguous flat fills with the same colour may be combined to produce one larger single flat fill, and contiguous flat fill primitives representing a linear gradient fill may be combined into a complex linear gradient fill of a type that can be rendered by a graphics rendering system. However, these known rendering methods of rendering all have disadvantages and limitations.
For example, known rendering methods that attempt to combine contiguous objects are limited to specified fill types available to a particular rendering module. Therefore, the only objects that can be combined are those that have the exact same fill type as each other. These types of objects do not occur often since a GDI layer such as the GDI 320 has no need to break these objects down in the first place.
For those methods that combine bitmaps, whole image fill data has to be copied to combine two different bitmaps into one bitmap. Copying image fill data can be a slow process, especially when a number of bitmaps are involved as a large number of memory allocations and a large amount of image data copying needs to be performed.
Those methods of rendering that combine flat fill primitives into complex equivalents are limited to outputting fills that are supported by a particular rendering module. One fill that is likely to be supported by a particular rendering module is a linear gradient fill, which is usually represented by two or three points and corresponding colour values at those points.
As described earlier, it is not atypical for the GDI 320 to pass a gradient fill as a number of flat filled parallelograms, with inconsistent parallelogram widths and non-constant colour changes. For gradient fills that are not linear, (eg., a non-linear gradient fill 510 as shown in FIG. 5A), known rendering methods attempt to combine the individual flat fill parallelograms into equivalent linear gradient components. Known rendering methods that compile non-linear gradient fill objects into linear gradient fills ideally produce two linear gradient fills. FIG. 5B shows two linear gradient fills 520 and 525, produced from the non-linear gradient fill 510 of FIG. 5A. Due to non constant colour changes and inconsistent parallelogram widths produced by the GDI 320 given the non-linear gradient fill 510, the known method of compiling gradient fills does not produce the ideal results of FIG. 5B since such a method cannot deal with inconsistencies within the gradient fill 510.
Conventional rendering methods often produce a large number of linear gradient fills 530-537, as shown in FIG. 5C. Producing such a large number of linear gradient fills can be less efficient than an original flat fill representation, ultimately slowing a rendering module down. The rendering module is slowed down because linear gradient fill pixel data is more difficult to calculate than that of a flat fill and since only a minimal number of edges are typically removed, the net effect is actually a slow down in rendering speed. Flat fills (eg., the flat fill rectangle 380) representing a gradient fill that arrive from the GDI 320 are not always consistent and do not always have reasonable linear colour change limits. Conventional methods of rendering are therefore very limited in handling flat fills in an efficient manner. Further, conventional rendering methods lack the ability to fully optimise graphic primitives because an associated rendering module lacks the available functionality.
A further disadvantage of rendering linear gradient fills occurs due to the fact that printers use subtractive primary colours cyan, magenta and yellow (CMY) and also black (K) to produce colour images on a page. As a result, it is necessary to convert a linear gradient fill stored in the RGB colour space to the CMYK colour space. The conversion of a linear gradient fill from the RGB colour space to the CMYK colour space can be done within a host computer or at a target device. However, a linear gradient fill that is described in terms of two or three points, each point having a corresponding colour value in the RGB colour space, can not be colour converted by simply converting the colour at each point since original colour data, passed by a GDI, does not map linearly into the colour converted colour space. That is, there is no linear relationship between the RGB colour space and the CMYK colour space. Conventional methods of colour converting a linear gradient fill, determine RGB values of pixel data for each pixel within the fill. Each of the pixels within the linear gradient fill are then converted into an equivalent CMYK colour value. The colour converted linear gradient fill is then added to a display list as a bitmap. Therefore, storing a linear gradient fill in the RGB colour space is very inefficient.
Thus, a need clearly exists for a more efficient method of rendering graphical objects.